#define _CRT_SECURE_NO_WARNINGS 1

//#include <stdio.h>
//#include <stdlib.h>
//#include <stdbool.h>
//
//typedef struct
//{
//	int* a;
//	int front;//指向头
//	int rear;//指向尾下一个
//	int k;
//} MyCircularQueue;
//
//MyCircularQueue* myCircularQueueCreate(int k)
//{
//	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//	//多开一个解决假溢出问题
//	obj->a = (int*)malloc(sizeof(int) * (k + 1));
//	obj->front = 0;
//	obj->rear = 0;
//	obj->k = k;
//
//	return obj;
//}
//
//bool myCircularQueueIsEmpty(MyCircularQueue* obj)
//{
//	return obj->front == obj->rear;
//}
//
//bool myCircularQueueIsFull(MyCircularQueue* obj)
//{
//	//int rearNext = obj->rear + 1;
//	//if (rearNext == obj->k + 1)
//	//{
//	//	rearNext = 0;
//	//}
//
//	//return rearNext == obj->front;
//
//	return (obj->rear + 1) % (obj->k + 1) == obj->front;
//}
//
//bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
//{
//	if (myCircularQueueIsFull(obj))
//	{
//		return false;
//	}
//
//	obj->a[obj->rear] = value;
//	obj->rear++;
//	obj->rear %= (obj->k + 1);
//	return true;
//}
//
//bool myCircularQueueDeQueue(MyCircularQueue* obj)
//{
//	if (myCircularQueueIsEmpty(obj))
//	{
//		return false;
//	}
//
//	obj->front++;
//	obj->front %= (obj->k + 1);
//	return true;
//}
//
//int myCircularQueueFront(MyCircularQueue* obj)
//{
//	if (myCircularQueueIsEmpty(obj))
//	{
//		return -1;
//	}
//	else
//	{
//		return obj->a[obj->front];
//	}
//}
//
//int myCircularQueueRear(MyCircularQueue* obj)
//{
//	if (myCircularQueueIsEmpty(obj))
//	{
//		return -1;
//	}
//	else
//	{
//		return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
//	}
//}
//
//void myCircularQueueFree(MyCircularQueue* obj)
//{
//	free(obj->a);
//	obj->a = NULL;
//	free(obj);
//}





//#include <stdio.h>
//#include <assert.h>
//#include <stdlib.h>
//#include <stdbool.h>
//
//typedef char STDataType;
//
//typedef struct Stack
//{
//	STDataType* a;
//	int top;
//	int capacity;
//}ST;
//
//void STInit(ST* ps)
//{
//	assert(ps);
//
//	ps->a = NULL;
//	ps->top = 0;
//	ps->capacity = 0;
//}
//
//void STDestroy(ST* ps)
//{
//	assert(ps);
//
//	free(ps->a);
//	ps->a = NULL;
//	ps->top = ps->capacity = 0;
//}
//
//void STPush(ST* ps, STDataType x)
//{
//	assert(ps);
//
//	if (ps->top == ps->capacity)
//	{
//		int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
//		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
//
//		if (NULL == tmp)
//		{
//			perror("realloc fail");
//			return;
//		}
//
//		ps->a = tmp;
//		ps->capacity = newcapacity;
//	}
//
//	ps->a[ps->top] = x;
//	ps->top++;
//}
//
//bool STEmpty(ST* ps)
//{
//	assert(ps);
//
//	return 0 == ps->top;
//}
//
//void STPop(ST* ps)
//{
//	assert(ps);
//	assert(!STEmpty(ps));
//
//	ps->top--;
//}
//
//STDataType STTop(ST* ps)
//{
//	assert(ps);
//	assert(!STEmpty(ps));
//
//	return ps->a[ps->top - 1];
//}
//
//int STSize(ST* ps)
//{
//	assert(ps);
//
//	return ps->top;
//}
//
//
//typedef struct
//{
//	ST pushst;
//	ST popst;
//} MyQueue;
//
//MyQueue* myQueueCreate()
//{
//	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
//	STInit(&obj->pushst);
//	STInit(&obj->popst);
//
//	return obj;
//}
//
//void myQueuePush(MyQueue* obj, int x)
//{
//	STPush(&obj->pushst, x);
//}
//
//int myQueuePeek(MyQueue* obj)
//{
//	if (STEmpty(&obj->popst))
//	{
//		//pushst的数据导入到popst
//		while (!STEmpty(&obj->pushst))
//		{
//			int top = STTop(&obj->pushst);
//			STPop(&obj->pushst);
//			STPush(&obj->popst, top);
//		}
//	}
//
//	return STTop(&obj->popst);
//}
//
//int myQueuePop(MyQueue* obj)
//{
//	int front = myQueuePeek(obj);
//	STPop(&obj->popst);
//
//	return front;
//}
//
//bool myQueueEmpty(MyQueue* obj)
//{
//	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
//}
//
//void myQueueFree(MyQueue* obj)
//{
//	STDestroy(&obj->popst);
//	STDestroy(&obj->pushst);
//	free(obj);
//}



//树的表示
//树的度是N
//#define N 6
//
//struct TreeNode
//{
//	int val;
//	struct TreeNode* subA[N];
//};


//struct TreeNode
//{
//	int val;
//
//	//顺序表
//	struct TreeNode** subA;
//	int size;
//	int capacity;
//};


//左孩子 右兄弟
struct TreeNode
{
	int val;
	struct TreeNode* leftChild;
	struct TreeNode* nextBrother;
};

//一个父亲如何找到他所有的孩子呢？